Virgin coconut oil (VCO) is known for its functional properties but it is yet to be widely developed into food products. Lipid and gelling agents are crucial ingredients for the rheological characteristics of milk puddings. This study aimed to explore the potential of blends of fish gelatin and sodium alginate as gelling agents and a delivery system for VCO. A total of 15 pudding formulations were generated from a mixture design approach to determine the optimized proportions of VCO (6-13%), fish gelatin (2-6%), sodium alginate (0.15-0.75%), and water (65-75%). All 15 pudding formulations exhibited strong elastic characteristic with their G’ (storage modulus) values higher than the G” (loss modulus). Formulations with high contents of gelatin (6%) and sodium alginate (0.28-0.75%) exhibited strong gel characteristics (tan δ < 0.1). The optimized formulation consisted of 10.68% VCO, 3.41% fish gelatin, 0.59% sodium alginate, and 68.33% water, with desirability of 0.874 against the viscoelastic properties and firmness of a commercial pudding. A significant increase was observed in firmness and free fatty acid (FFA) value of the optimized pudding from 3 weeks onwards, over the weekly evaluation of 4 weeks storage at 4 ± 1°C. The sensory assessment showed that rancidity of pudding was not significantly detected by panels throughout the 4 weeks of storage period.