The laminar burning velocities were measured for mixtures of CH4/O-2/N-2/carbon black particle with equivalence ratio values in the range of 0.8-1.2. The data were acquired at an initial pressure 0.1 MPa and initial temperatures of 303, 353, and 403 K. High-speed schlieren visualization, used to monitor flame growth following provided a direct determination of the laminar flame velocity. The data were corrected for flame stretch, providing the unstretched laminar burning velocities and burned gas Markstein lengths. The values measured for CH4/O-2/N-2 flames were compared to those previously reported in the literature and computational prediction using the full mechanism. These comparisons revealed reasonable similarity in the data and demonstrated the reliability of the current experimental system and the accuracy of the full mechanism for CH4/O-2/N-2 flames. A decline in the Markstein lengths and burning velocities and an enhancement of the thermal diffusive instability upon the addition of carbon black particles were shown by the data. An early onset of cellularity preceded by the formation of toroidal cells for CH4/O-2/N-2/carbon black particle flames indicated particle mediated alteration of the Cellular flame structure. The key reactions involved in the observed changes in the laminar burning velocities were-identified on the basis of the sensitivity analysis.