Στο πρωτάθλημα της Γ΄ κατηγορίας 2015-16 συμμετείχαν 16 ομάδες. Όλες οι ομάδες αναμετρήθηκαν αναμεταξύ τους από δύο φορές, μία εντός και μία εκτός έδρας. Πρωταθλήτρια ανακηρύχθηκε η ομάδα που συγκέντρωσε τους περισσότερους βαθμούς. Οι τρεις πρώτες ομάδες προβιβάστηκαν στο πρωτάθλημα Β΄ κατηγορίας 2016-17. Οι τρεις τελευταίες ομάδες υποβιβάστηκαν στο πρωτάθλημα Επίλεκτη κατηγορία ΣΤΟΚ 2016-17.[3][4] Ωστόσο, μετά το τέλος του πρωταθλήματος αποχώρησε μία ομάδα από το πρωτάθλημα Γ΄ κατηγορίας 2016-17 και έτσι η τρίτη από το τέλος ομάδα του πρωταθλήματος Γ΄ κατηγορίας 2015-16 δεν υποβιβάστηκε.[5]
Σύστημα βαθμολόγησης
Η νίκη βαθμολογείται με 3 βαθμούς και η ισοπαλία με 1 βαθμό ενώ η ήττα δεν δίνει κανένα βαθμό.
Το σύστημα βαθμολόγησης που ίσχυε ήταν: Νίκη=3 βαθμοί, Ισοπαλία=1 βαθμός, Ήττα=0 βαθμοί
Κανόνες βαθμολογίας: 1ος Βαθμοί, 2ος Μεταξύ των ισόβαθμων ομάδων αγώνες (i. Βαθμοί από τα μεταξύ των ισόβαθμων ομάδων παιχνίδια, ii. Διαφορά τερμάτων σε μεταξύ των ισόβαθμων ομάδων παιχνίδια, iii. Καλύτερη εκτός έδρας επίθεση στα μεταξύ των ισόβαθμων ομάδων παιχνίδια), 3ος Γενική διαφορά τερμάτων, 4ος Καλύτερη επίθεση.
1Ο αγώνας ΑΠΕΠ-Ηρακλής έληξε με σκορ 2-2. Ωστόσο, κατακυρώθηκε με τέρματα 0-3 υπέρ του Ηρακλή μετά από απόφαση του Αθλητικού Δικαστή λόγω αντικανονικής συμμετοχής δύο ποδοσφαιριστών της ΑΠΕΠ.[7]