Problem solving is an indispensable part of engineering. Improving critical thinking dispositions for solving engineering problems is one of the objectives of engineering education. In this sense, knowing critical thinking and problem solving skills of engineering students is of importance for engineering education. This study aims to determine the critical thinking dispositions and the problem solving skills of computer engineering students as well as the relationship between them. The study was conducted in a university located in the north of Turkey at the beginning of the 2013-2014 spring semester. The research sample consisted of 186 students attending the faculty of engineering department of computer engineering. The California Critical Thinking Dispositions Inventory (CCTDI) and the Problem Solving Inventory (PSI) were used for data collection. The descriptive survey model was employed. The data obtained in the study were analyzed via the independent t-test, the Mann Whitney U-test, the Kruskal-Wallis test, and the Pearson's Correlation coefficient. The research results indicated that the students had high-level critical thinking dispositions and problem solving skills. Critical thinking disposition levels of the students did not vary statistically significantly by gender and grade. Similarly, no statistically significant variation was observed in the problem solving skill levels of the students by gender and grade. In addition, a statistically significant relationship was found between the critical thinking dispositions and the problem solving skills of students, but it was a low-level relationship.