Optimal packaging and storage conditions for fresh tilapia fillets were established by evaluating sensory and microbiological changes, as well as monitoring physicochemical properties. Nile tilapia (Oreochromis niloticus) farmed in recirculation aquaculture system was filleted, deskinned, and packaged in air and 50% CO2/50% N2 prior to chilling and superchilling storage at 1°C and −1°C. Sensory analysis of cooked samples revealed a shelf life of 13–15 days for air-packaged fillets during storage at 1°C and 20 days at −1°C. At the end of shelf life in air-packaged fillets, total viable counts (TVC) and pseudomonads counts reached log 8 colony-forming units (CFU) g−1. In 50% CO2/50% N2-packaged fillets, the lag phase and generation time of bacteria were extended and recorded counts were below the limit for consumption (<log 8 CFU g−1) after 23 days of storage at both 1°C and −1°C. However, modified atmosphere (MA) packaging negatively affected color characteristics of the fillets soon after packaging (day 6). Color is an important indicator of tilapia fillets quality and a major factor in influencing retail purchase decisions. In view of that, air packaged at −1°C storage temperature was the optimal condition for fresh tilapia fillets. Total volatile basic nitrogen (TVB-N) and trimethylamine (TMA) were not good indicators of spoilage of tilapia fillets in this study.