Background: Chronic non-specific low back pain is a non-harmous condition often found in the general population. It is one of the most significant disabilities and needs different treatment modalities. This study investigates the effects of pain neuroscience education and physiotherapy on pain intensity, fear of movement and functional status in a Lithuanian cohort with non-specific low back pain. Methods: The study was performed at the primary health care unit in Kaunas, Lithuania. The key inclusion criterion was persistent non-specific low back pain longer than three months and which affects daily life functions. Thirty participants (mean 33.47, SD 4.38 years age, 70% women) were randomised into two training groups with and without pain neuroscience education (for a total of 60 min of teaching). Physiotherapy was performed twice per week during 45 min/session for a period of 10 weeks with exercises which strengthen, stabilize, and stretch the spinal cord muscles. Outcomes included pain intensity, kinesiophobia and disability and these were measured by self-scored questionnaires (numeric rating scale, Tampa scale for kinesiophobia-11, Oswestry disability index and the Roland–Morris questionnaire, respectively). Results: The results indicate that both groups improved in the measured outcomes, with the only difference between them being a better improvement in kinesiophobia in the group receiving physiotherapy and pain neuroscience education. Conclusions: The results of this study confirm that a relatively short intervention of pain neuroscience education enhances the effects of physiotherapy and should be implemented in clinical practice.