Fish market wastewater (FMWW) releases a high amount of organic and nutrient load to the water environment. Untreated FMWW is detrimental for the aquatic environment. A necessary bacterial culture was acclimated in the laboratory to investigate feasibility of anaerobic treatment for real-life FMWW. FMWW was collected 30 times. The average values of total dissolved solids (TDS), pH, total suspended solids (TSS), biochemical oxygen demand (BOD), chemical oxygen demand (COD), PO43−, NO3−–N, oil and grease and NH4+–N were found to be 4100 mg/L, 6.43, 75 mg/L, 3000 mg/L, 4200 mg/L, 120 mg/L, 55 mg/L, 22 mg/L and 450 mg/L respectively after the two-step pretreatment process. A combined removal of COD and NO3−–N was studied in a laboratory scale packed bed up-flow anaerobic fixed film reactor (AFFR). To attach the acclimated microorganisms, earthen potter’s clay of 12 mm inner diameter annular rings were utilized as packing. KNO3 and NH4NO3 solutions were used in varied proportions to prepare a synthetic substrate as nitrate source whereas sucrose was used as organic carbon. Experimental results revealed that the highest nitrate removal of about 85% was obtained for an influent NO3−–N of 30 mg/L in the presence of an initial COD concentration of 3500 mg/L for 4 L/day of hydraulic loading, whereas maximum COD removal of 82% was achieved for 3500 mg/L of initial COD concentration, at 2 days hydraulic retention time (HRT). Methane generation in the reactor was found to be low in the presence of a high NO3−–N level.