Background The occurrence of the Coronavirus Disease 2019 (COVID-19) affects the mental health situation of almost everyone, including University students who spent most of their time at home due to the closure of the Universities. Therefore, this study aimed at assessing depression, anxiety, stress and identifying their associated factors among university students in Ethiopia during the early stage of the COVID-19 pandemic. Methods We invited students to complete an online survey using Google forms comprising consent, socio-demographic characteristics, and the standard validated depression, anxiety, and stress scale (DASS-21) questionnaire. After completion of the survey from June 30 to July 30, 2020, we exported the data into SPSS 22. Both descriptive and analytical statistics were computed. Associated factors were identified using binary logistic regression and variables with a p-value <0.05 were declared as statistically significant factors with the outcome variables. Results A total of 423 students completed the online survey. The prevalence of depression, anxiety, and stress in this study was 46.3%, 52%, and 28.6%, respectively. In the multivariable model, female sex, poor self-efficacy to prevent COVID-19, those who do not read any material about COVID-19 prevention, lack of access to reading materials about their profession, and lack of access to uninterrupted internet access were significantly associated with depression. Female sex, lower ages, students with non-health-related departments, those who do not think that COVID-19 is preventable, and those who do not read any materials about COVID-19 prevention were significantly associated with anxiety. Whereas, being female, students attending 1^st and 2^nd years, those who do not think that COVID-19 is preventable, presence of confirmed COVID-19 patient at the town they are living in, and lack of access to reading materials about their profession were significantly associated with stress. Conclusions Depression, anxiety, and stress level among University students calls for addressing these problems by controlling the modifiable factors identified and promoting psychological wellbeing of students.