The objective of this study is to identify problem nutrients and to develop food-based recommendations (FBRs) and nutrient-dense menus based on the nutrient gaps. This study was conducted among male workers (n = 31) in an oil and gas worksite in East Kalimantan, Indonesia. Body weight, height, waist circumference, as well as systolic and diastolic blood pressure were measured. Weekly food consumption patterns were assessed using 1 day 24 h dietary recall (24HR), 1 day weighed food record (WFR), and 5 day food tally. Linear programming (LP) analysis using WHO Optifood software was used to identify problem nutrients and develop FBRs. The identified nutrient gaps were inserted in the nutrient-dense menu for the worksite canteen. Obesity, central obesity, and hypertension were reported in 64.5%, 48.4%, and 3.2% of the workers. Calcium, folate, total PUFA, n-6 PUFA, and dietary fiber were identified as problem nutrients. The FBRs can improve the intake of problem nutrients from 20% of recommended nutrient intake (RNI) in the nonoptimized diet to 50–70% RNI in the optimized diet, while controlling the intake of sodium and saturated fat within an acceptable range. The remaining nutrient gaps (calcium, total PUFA, n-6 PUFA, and dietary fiber) were inserted into the 14-day modified canteen snack menu. This study provides initial evidence that a combination of FBRs and a modified canteen menu can optimize the diet of the workers. Further studies assessing the effectiveness of the developed FBRs and modified menus are needed.