Phaolô Tịnh Nguyễn Bình Tĩnh
Thời kỳ linh mục

Ngày 31 tháng 5 năm 1960, Phaolô Tịnh Nguyễn Bình Tĩnh được thụ phong chức linh mục tại Thị Nghè, Sài Gòn, do giám mục Simon Hòa Nguyễn Văn Hiền chủ phong. Tân linh mục là linh mục thuộc linh mục đoàn Hạt Đại diện Tông Tòa Kon Tum. Sau khi thụ phong, ngày 13 tháng 6 năm 1961, ông gia nhập hội linh mục Xuân Bích, làm công tác huấn luyện đào tạo chủng sinh. Linh mục Tĩnh là linh mục của giáo phận Kon Tum trong vòng hơn một năm trước khi gia nhập hội linh mục Xuân Bích, từ năm 1960 đến năm 1961.
Linh mục Nguyễn Bình Tĩnh được cử đi du học tại Đại học Công giáo Paris, Pháp từ năm 1960 đến năm 1964 về Thần học. Sau khi tốt nghiệp năm 1964, ông trở về Việt Nam và được bổ nhiệm làm giáo sư Đại chủng viện Xuân Bích Nha Trang và Huế. Tại chủng viện Huế, ông cũng chịu trách nhiệm về nguồn ngân quỹ cho chủng viện (Econome) và là giáo sư các môn Xã hội học và Phụng Tự.
Năm 1970, linh mục Phaolô Tịnh Nguyễn Bình Tĩnh được chọn làm giám đốc Tiểu chủng viện Thánh Gioan, Đà Nẵng. Tại chủng viện này, ông giảng dạy các môn Tín lý và Khoa học Tự nhiên. Các chủng sinh được ông hỗ trợ trong tư cách một người cha, thường tham gia các buổi họp phụ huynh cho các tiểu chủng sinh. Do vậy, các tiểu chủng sinh gọi ông với cái tên bố Đốc (viết tắt của Cha giám đốc). Trong thời gian linh mục, linh mục Nguyễn Bình Tĩnh từng đóng vai trò trợ phong trong nghi thức truyền chức giám mục Phanxicô Xaviê Nguyễn Quang Sách, được tổ chức vào năm 1975. Linh mục Tĩnh giảng dạy tại Tiểu chủng viện Đà Nẵng cho đến năm 1984. Trong thời gian này, ông còn là Tổng Đại diện giáo phận Đà Nẵng, chức vụ ông giữ từ năm 1977 đến năm 1987. Từ năm 1987 đến năm 1994, ông là chủ tịch Hội đồng Linh mục giáo phận Đà Nẵng.
Đồng thời với chức chủ tịch Hội đồng Linh mục, linh mục Bình Tĩnh kiêm nhiệm chức vụ linh mục quản xứ giáo xứ An Hải từ năm 1987 đến năm 1994. Trang tin Việt Nam Thời Báo, website của Hội Nhà báo Độc lập Việt Nam trích bài đăng bản tiếng Việt của bài viết An Analysis of the Vietnamese Communist Party’s suppression of the Catholic Church (Bản phân tích việc đàn áp Giáo hội Công giáo của Đảng Cộng sản Việt Nam) được viết năm 2002 bởi linh mục Trần Xuân Tâm. Linh mục Tâm được Hội nhà Báo Độc lập Việt Nam trích dẫn viết trong bài viết rằng linh mục Nguyễn Bình Tĩnh là một người ủng hộ chính quyền một cách "công khai và hăng say", thông qua ví dụ là dùng văn kiện của Đảng trong bài giảng. Cũng trong bài viết này, giáo dân An Hải đuợc trích dẫn rằng linh mục Tĩnh đã chấp nhận cho một viên chức chính quyền đến mời gọi giáo dân tham gia chương trình trái phiếu chính phủ vào một ngày Chúa nhật năm 1991. Hai năm sau, tháng 3 năm 1993, cũng trong bối cảnh thánh lễ Công giáo, linh mục Tĩnh đã hỗ trợ phân phát tài liệu [truyên truyền] về tránh thai nhân tạo và phá thai.
Cũng theo tài liệu của linh mục Trần Xuân Tâm, một trong những điều kiện để mở lại Đại chủng viện là linh mục Nguyễn Bình Tĩnh được đặt làm giám đốc Chủng viện. Năm 1994, linh mục Tĩnh được chọn làm giám đốc Đại chủng viện Xuân Bích Huế và đã giữ chức vụ này đến khi được chọn làm giám mục. Ông là giám đốc chủng viện đầu tiên, sau một thời gian chủng viện phải ngưng hoạt động. Đại chủng viện Xuân Bích Huế thời gian này đào tạo giáo sĩ cho ba giáo phận Đà Nẵng, Huế và Kon Tum. Ngoài các chức vụ trên, ông còn là thành viên Ban Cố vấn giáo phận.
Theo tài liệu của linh mục Trần Xuân Tâm do Hội Nhà báo Độc lập Việt Nam đăng tải nêu thông tin giáo dân có biết đến một văn thư từ Công an Đà Nẵng gửi cho linh mục Tĩnh và gọi ông là "giám mục" trong giai đoạn khoảng năm 1995 và 1996. Tài liệu này cũng cho rằng chính quyền đã sắp xếp bằng phương cách "hộ khẩu", buộc các linh mục giáo phận Đà Nẵng giảng dạy tại Huế phải chuyển hộ khẩu đến Huế, trừ trường hợp của linh mục Tĩnh. Các linh mục có hộ khẩu Huế sau đó bị chính quyền từ chối đề cử giám mục bởi lý do "tình trạng thường trú" ngoài địa giới Đà Nẵng. Linh mục Tâm cũng cho rằng giám mục Phanxicô Xaviê Nguyễn Quang Sách, tuy cần một giám mục kế vị hoặc ít nhất là một giám mục phó, không mong muốn và không đề cử linh mục Nguyễn Bình Tĩnh làm giám mục do nghi ngại việc này sẽ gây "nguy hại cho Giáo hội".