A sensitive, specific, and miniaturized non-enzymatic cholesterol sensor was prepared based on the competition of inclusion complex formation between β-cyclodextrin (BCD) and cholesterol, and between BCD and methylene blue (MB). BCD was immobilized on the surface of Fe3O4 magnetic nanoparticles instead of the electrode surface to increase the kinetic rate and enhance the sensitivity of the sensor. Furthermore, the use of magnetic nanocomposites and a screen-printed carbon electrode reduces the overall analysis time and simplifies the sample measurement procedures, making the sensor suitable for point-of-care analysis. The electrochemical measurement results of MB, released from the reactions between BCD and solutions containing various concentrations of cholesterol were used as the input signal to calculate the cholesterol concentrations. A good linearity as well as an excellent accuracy and repeatability in the concentration range of 0-150 μM with an estimated limit of detection of 2.88 μM could be achieved by using the amperometric technique at a constant potential of -0.43 V. The sensor showed a good selectivity in the presence of 1 mM concentrations of interfering agents, including NaCl, CaCl2, glycine, glucose, and ascorbic acid. Furthermore, a validation performed for cholesterol determination in milk samples was in agreement with the measurements performed by using the HPLC method, suggesting that the developed sensor is reliable.