Objective: To construct and validate a computer-based and performance-based instrument to assess health literacy skills for informed decision making in colorectal cancer screening among screening invitees. Methods: An instrument was constructed based on a conceptual framework of health literacy skills in colorectal cancer screening and findings from an expert survey. The instrument was field-tested among individuals with low health literacy (n = 28). Its validity and reliability was assessed using classical test theory and item response theory approaches in an online panel of colorectal cancer screening invitees (n = 696). Results: Confirmatory factor analysis confirmed four separate factors: Comprehension, Application, Numeracy and Communication. A fifth domain (Appraisal) demonstrated poor reliability and validity and was omitted in further analyses. Internal consistency (Cronbach's alpha > 0.6 for the four scales) was acceptable and test-retest reliability was moderate. The four factors were measurement invariant for age, sex and educational level. Conclusion: The computer-based measures were acceptable for self-administration. The constructed multidimensional health literacy instrument showed acceptable measurement properties. Practice implications: Our findings imply that the computer-based instrument can be used for the development of interventions to support informed decision making about colorectal cancer screening among individuals with varying health literacy levels. Further research is needed for optimizing performance-based measurement of the Appraisal and Communication domains.