LỊCH SỬ HÌNH THÀNH
Được thành lập ngày 28 tháng 9 năm 1976 theo Quyết định số 464/TC-UB của Ủy ban nhân dân tỉnh Phú Khánh thành lập Ban Tổ chức Chính quyền tỉnh Phú Khánh. Theo đó, Ban Tổ chức chính quyền tỉnh Phú Khánh là cơ quan chuyên môn của Ủy ban nhân dân tỉnh, đặt dưới sự lãnh đạo trực tiếp, toàn diện của Ủy ban nhân dân tỉnh, đồng thời là cơ quan chuyên môn cấp dưới của Ban Tổ chức Chính phủ, chịu sự chỉ đạo, hướng dẫn của Ban Tổ chức Chính phủ. Đồng thời, dưới sự lãnh đạo và chỉ đạo của Tỉnh ủy và Ủy ban nhân dân tỉnh, sự hướng dẫn của Ban Tổ chức Chính phủ và kết hợp chặt chẽ với Ban Tổ chức Tỉnh ủy, Ban Tổ chức chính quyền tỉnh có nhiệm vụ giúp Ủy ban nhân dân tỉnh nghiên cứu hướng dẫn công tác xây dựng và củng cố chính quyền các cấp; hướng dẫn việc xây dựng, kiện toàn tổ chức bộ máy các cơ quan chuyên môn của tỉnh và huyện; quản lý biên chế khu vực hành chính sự nghiệp; quản lý về mặt nhà nước việc thực hiện những chủ trương, chính sách và nghị quyết của các cấp ủy Đảng về công tác cán bộ bao gồm các việc điều động, bổ nhiệm, đề bạt, đào tạo, bồi dưỡng, tuyển sinh, tuyển dụng.
Tổ chức bộ máy của Ban Tổ chức Chính quyền tỉnh Phú Khánh được cơ cấu gồm: Lãnh đạo ban: Có trưởng ban và các phó trưởng ban giúp việc; các phòng nghiệp vụ gồm: Phòng Xây dựng chính quyền cơ sở; Phòng Tổ chức biên chế, Phòng quản lý cán bộ; Phòng đào tạo tuyển sinh; Văn phòng ban.
Đến năm 1988, thi hành Nghị quyết số 34-NQ/TW ngày 02/7/1986 của Bộ Chính trị về kiện toàn tổ chức, nâng cao hiệu lực của bộ máy đáp ứng yêu cầu của nhiệm vụ kinh tế xã hội, Ủy ban nhân dân tỉnh đã ban hành Quyết định số 1153/UB ngày 19/7/1988 kiện toàn tổ chức bộ máy Ban Tổ chức chính quyền tỉnh Phú Khánh. Theo đó, Ban Tổ chức chính quyền tỉnh Phú Khánh là cơ quan giúp việc trực tiếp cho Ủy ban nhân dân tỉnh thống nhất quản lý công tác tổ chức và biên chế, công tác xây dựng củng cố chính quyền, công tác cán bộ, công tác tuyển sinh và đào tạo bồi dưỡng thuộc khu vực nhà nước theo đúng chính sách, pháp luật của Đảng và Nhà nước.
Thực hiện Nghị quyết số 02/2002/QH11 của Quốc hội quy định danh sách các Bộ và cơ quan ngang Bộ, trong đó, Ban Tổ chức Chính phủ được đổi tên thành Bộ Nội vụ. Căn cứ Quyết định số 248/2003/QĐ-TTg ngày 20 tháng 11 năm 2003 của Thủ tướng Chính phủ về việc đổi tên Ban Tổ chức chính quyền thuộc Ủy bân nhân dân tỉnh, thành phố trực thuộc Trung ương, ngày 31 tháng 11 năm 2003, Chủ tịch Ủy ban nhân dân tỉnh ban hành Quyết định số 899/QĐ-CT về việc đổi tên Ban Tổ chức chính quyền tỉnh Khánh Hòa thành Sở Nội vụ tỉnh Khánh Hòa. Trên cơ sở Thông tư số 05/2004/TT-BNV ngày 19 tháng 01 năm 2004 của Bộ Nội vụ hướng dẫn chức năng, nhiệm vụ, quyền hạn và cơ cấu tổ chức cơ quan chuyên môn giúp UBND quản lý nhà nước về công tác nội vụ ở địa phương, ngày 05 tháng 7 năm 2004, Ủy ban nhân dân tỉnh đã ban hành Quyết định số 153/QĐ-UBND về việc kiện toàn chức năng, nhiệm vụ, quyền hạn và cơ cấu tổ chức của Sở Nội vụ. Theo đó, Sở Nội vụ tỉnh Khánh Hòa là cơ quan chuyên môn của Uỷ ban nhân dân tỉnh có chức năng tham mưu và giúp Uỷ ban nhân dân tỉnh quản lý nhà nước về nội vụ, bao gồm các lĩnh vực: Tổ chức bộ máy các cơ quan hành chính, sự nghiệp, tổ chức chính quyền địa phương; địa giới hành chính; cán bộ, công chức, viên chức nhà nước, cán bộ công chức xã, phường, thị trấn; tổ chức hội và tổ chức phi Chính phủ, các dịch vụ công thuộc phạm vi quản lý của Sở; và chịu sự chỉ đạo, quản lý về tổ chức, biên chế và công tác của Uỷ ban nhân dân tỉnh; đồng thời chịu sự chỉ đạo, hướng dẫn, kiểm tra về chuyên môn, nghiệp vụ của Bộ Nội vụ.
Cơ cấu tổ chức Sở Nội vụ gồm: Lãnh đạo Sở; Phòng Hành chính – Tổng hợp; Phòng Tổ chức bộ máy và Cải cách hành chính; Phòng Cán bộ, công chức và Đào tạo; Phòng Xây dựng chính quyền; Thanh tra Sở (được thành lập theo Quyết định số 172/QĐ-UBND ngày 28/5/2004).
Năm 2008, do yêu cầu cải cách bộ máy theo quy định của Nghị định số 13/2008/NĐ-CP ngày 04/02/2008 của Chính phủ quy định tổ chức các cơ quan chuyên môn thuộc UBND tỉnh, Sở Nội vụ Khánh Hòa tiếp nhận tổ chức và nhiệm vụ của Ban Thi đua - Khen thưởng, Ban Tôn giáo, Trung tâm lưu trữ tỉnh để trở thành Sở có chức năng quản lý đa ngành, đa lĩnh vực.
Ngày 24/6/2008, Ủy ban nhân dân tỉnh ban hành Quyết định số 1608/QĐ-UBND kiện toàn chức năng, nhiệm vụ, quyền hạn và cơ cấu tổ chức của Sở Nội. Theo đó, Sở Nội vụ được bổ sung thêm các nhiệm vụ tham mưu, giúp Ủy ban nhân dân tỉnh thực hiện chức năng quản lý nhà nước về văn thư, lưu trữ nhà nước; tôn giáo; thi đua – khen thưởng; và cơ cấu tổ chức có sự thay đổi: Phòng Hành chính – Tổng hợp được đổi tên thành Văn phòng Sở; Phòng Cán bộ, Công chức và Đào tạo; Phòng Tổ chức bộ máy và Cải cách hành chính; Phòng Xây dựng chính quyền; thành lập mới Phòng Quản lý Văn thư, Lưu trữ; Ban tôn giáo; Ban Thi đua – Khen thưởng; Trung tâm Lưu trữ.
Để đáp ứng yêu cầu nhiệm vụ trong tình hình mới và nhằm tiếp tục kiện toàn chức năng, nhiệm vụ của Sở Nội vụ theo quy định tại Thông tư số 04/2011/TT-BNV, Ủy ban nhân dân tỉnh đã ban hành Quyết định kiên toàn cơ cấu tổ chức, theo đó, Phòng Cán bộ, Công chức và Đào tạo được đổi tên thành Phòng Cán bộ, Công chức – Viên chức và Đào tạo; Phòng Tổ chức – Biên chế; Phòng Cải cách hành chính được thành lập trên cơ sở tách ra từ Phòng Tổ chức bộ máy và Cải cách hành chính; Chi cục Văn thư – Lưu trữ được thành lập trên cơ sở Phòng Quản lý Văn thư, Lưu trữ; Trung tâm Lưu trữ; và thành lập mới Phòng Công tác thanh niên.
Thực hiện Thông tư số 15/2015/TT-BNV ngày 31 tháng 10 năm 2014 của Bộ Nội vụ hướng dẫn chức năng, nhiệm vụ, quyền hạn và cơ cấu tổ chức của Sở Nội vụ thuộc Ủy ban nhân dân tỉnh, thành phố trực thuộc Trung ương; Phòng Nội vụ thuộc UBND huyện, quận, thị xã, thành phố thuộc tỉnh, ngày 24/3/2015, Ủy ban nhân dân tỉnh ban hành Quyết định số 692/QĐ-UBND kiện toàn chức năng, nhiệm vụ, quyền hạn và cơ cấu tổ chức của Sở Nội vụ. Theo đó, về chức năng, nhiệm vụ, quyền hạn của Sở Nội vụ về cơ bản không có sự thay đổi; cơ cấu tổ chức có một số thay đổi (Lãnh đạo Sở: có Giám đốc và 03 Phó Giám đốc; các đơn vị thuộc Sở: Phòng Tổ chức – Biên chế được đổi tên thành Phòng Tổ chức, Biên chế và Tổ chức phi chính phủ; Phòng Cán bộ, Công chức – Viên chức và Đào tạo được đổi tên thành Phòng Công chức, Viên chức; Phòng Xây dựng chính quyền và Công tác thanh niên được thành lập trên cơ sở Phòng Xây dựng chính quyền và Phòng Công tác thanh niên; Phòng Cải cách hành chính; Văn phòng; Thanh tra; các cơ quan trực thuộc Sở: Ban Thi đua – Khen thưởng; Ban Tôn giáo; Chi cục Văn thư – Lưu trữ). Ngày 03/7/2020 Ủy ban nhân dân tỉnh ban hành Quyết định số 1617/QĐ-UBND về việc kiện toàn cơ cấu tổ chức của Sở Nội vụ tỉnh Khánh Hòa; theo đó, về cơ cấu tổ chức có sự thay đổi (Lãnh đạo Sở: có Giám đốc và 03 Phó Giám đốc; các đơn vị thuộc Sở: hợp nhất Phòng Tổ chức, Biên chế và Tổ chức phi chính phủ với Phòng Cán bộ, Công chức – Viên chức và Đào tạo thành Phòng Tổ chức, biên chế - Công chức, viên chức; Phòng Xây dựng chính quyền và Công tác thanh niên; Phòng Cải cách hành chính; Văn phòng; Thanh tra; các cơ quan trực thuộc Sở: Ban Thi đua – Khen thưởng; Ban Tôn giáo; Chi cục Văn thư – Lưu trữ)
Ngày 28/4/2021 Ủy ban nhân dân tỉnh ban hành Quyết định số 1145/QĐ-UBND về việc kiện toàn cơ cấu tổ chức của Sở Nội vụ tỉnh Khánh Hòa; theo đó, về cơ cấu tổ chức có sự thay đổi (Lãnh đạo Sở: có Giám đốc và 03 Phó Giám đốc; các đơn vị thuộc Sở: Phòng Tổ chức, biên chế - Công chức, viên chức; Phòng Xây dựng chính quyền và Công tác thanh niên; Phòng Cải cách hành chính; Văn phòng; Thanh tra; Phòng Thi đua – Khen thưởng; Phòng Văn thư – Lưu trữ; các cơ quan, đơn vị trực thuộc Sở: Ban Tôn giáo; Trung tâm Lưu trữ lịch sử)