Typical colloid-polymer composites have particle diameters much larger than the polymer mesh size, but successful integration of smaller colloids into a large-mesh network could allow for the realization of new colloidal states of spatial organization and faster colloid motion which can allow the possibility of switchable re-configuration of colloids or more dramatic stimuli-responsive property changes. Experimental realization of such composites requires solving non-trivial materials selection and fabrication challenges; key questions include composition regime maps of successful composites, the resulting structure and colloidal contact network, and the mechanical properties, in particular the ability to form a network and retain strain stiffening in the presence of colloids. Here, we study these fundamental questions by formulating composites with fluorescent (though not stimuli-responsive) carboxylate modified polystyrene/latex (CML) colloidal particles (diameters 200 nm and 1000 nm) in bovine fibrin networks (a semi-flexible biopolymer network with mesh size 1-5 μm). We describe and characterize two methods of composite preparation: adding colloids before fibrinogen polymerization (Method I), and electrophoretically driving colloids into a network already formed by fibrinogen polymerization (Method II). We directly image the morphology of colloidal and fibrous components with two-color fluorescent confocal microscopy under wet conditions and SEM of fixed dry samples. Mechanical properties are studied with shear and extensional rheology. Both fabrication methods are successful, though with trade-offs. Method I retains the nonlinear strain-stiffening and extensibility of the native fibrin network, but some colloid clustering is observed and fibrin network integrity is lost above a critical colloid concentration that depends on fibrinogen and thrombin concentration. Larger colloids can be included at higher volume fractions before massive aggregation occurs, indicating surface interactions as a limiting factor. Method II results in a loss of measurable strain-stiffening, but colloids are well dispersed and template along the fibrous scaffold. The results here, with insight into both structure and rheology, form a foundational understanding for the integration of other colloids, e.g. with stimuli-responsive functionalities, into semi-flexible networks.