Whereas the assessment of complex problem solving (CPS) has received increasing attention in the context of international large-scale assessments, its fairness in regard to students' cultural background has gone largely unexplored. On the basis of a student sample of 9th-graders (N = 299), including a representative number of immigrant students (N = 127), the present study evaluated (a) whether CPS can be assessed fairly among students with or without immigration background and (b) whether achievement differences between these groups exist. Results showed that fair assessment of CPS is possible using the Genetics Lab, a computer-based microworld that incorporates game-like characteristics and multilingual-friendly features. Immigrant students were generally outperformed by their nonimmigrant peers, but performance differences can largely be explained by differential enrollment in lower academic tracks. Interestingly, CPS scales were less affected by students' educational background than a traditional paper-pencil-based reasoning scale. Moreover, a fine-grained analysis of different facets of CPS showed that irrespective of the academic track, immigrant students demonstrated a more efficient task exploration behavior than their native peers (d = 0.26). In sum, this might point to the potential of computer-based assessment of CPS to identify otherwise hidden cognitive potential in immigrant students.