EU and national legislation constantly establishes new obligations for food business operators (FBOs). In order to study the implementation and potential problems in implementing food legislation, a questionnaire was sent to small- and medium-size meat and fish FBOs (n = 904) in Finland found in the register of the National Food Safety Authority Evira. The total response rate was 27.6%. In addition, 18 different FBOs that had gone through the process of approval for meat and fish establishments between 2005 and 2006 were interviewed.The results showed that FBOs in the meat and fish sector have both common and differing experiences of the problems caused by the food legislation requirements. Most common problems concerning food safety legislation are related to the layout of production premises and transport routes, control fees, requirements concerning in-house control, structures and maintenance of premises and varying interpretation of food safety legislation. Small FBOs saw the requirements of food legislation as more onerous than medium-sized FBOs. Small FBOs mentioned the requirements concerning in-house control and approval of the in-house control plan, labelling and traceability as problematic for their operations. On the other hand, medium-sized FBOs experienced problems relating to the requirements for building materials as such, by-products and waste management, in addition to layout of production premises and transport routes, structures and maintenance of facilities and the HACCP system.