Recently a significantly interest in nanotechnology has triggered research in the area of micro/nanofibers based on composite materials. Cellulose is considered to be the most important natural renewable polymeric raw material. In these applications cellulose can be regarded as an attractive option as reinforcing material due to its abundant availability and biodegradability. Therefore, we have used cellulose nanocrystals obtained after acid hydrolysis of cellulose fibers as nanofiller in hydrophobic microfiber polymer matrices. The microfiber matrices were obtained via electrospinning of fluid jet subject to a critical electric field. The microfibers and nonwoven structures obtained were characterized by their high porosity and surface-to-volume ratio, which is essential for applications such as separation membranes, scaffolds for tissue engineering, wound dressing materials, artificial blood vessels, and sensors. Both of these characteristics are often required in high-performance applications. We discuss the unique opportunities of the obtained composites in terms of stiffness and strength as well as the possibility of subsequent surface chemical modification. Thermal and mechanical testing of the nanofibers webs were carried out to analyze their potential functionalities of the composites. The results indicated that a strong filler-polymer matrix interaction is developed during the electrospinning process between the whiskers and the polymer matrix. The main effect of the filler is a significant increase of the storage modulus of composites based on electrospun microfibers.