This paper presents a novel analytical formulation for identifying the closest pair of points lying on two arbitrary cylinders in space, and subsequently the distance between them. Each cylinder is decomposed into four geometric primitives. It is shown that the original problem reduces to the computation of the shortest distance between five distinct combinations of these primitives. Four of these subproblems are solved in closed form, while the remaining one requires the solution of an eight-degree polynomial equation. The analytical nature of the formulation and solution allows the identification of all the special cases, e.g., positive-dimensional solutions, and the curve of intersection when the cylinders interfere. The symbolic precomputation of the results leads to a fast numerical implementation, capable of solving the problem in about 50 ls (averaged over 1×106 random instances of the most general case) on a standard PC. The numerical results are verified by repeating all the calculations in a general-purpose commercial CAD software. The algorithm has significant potential for applications in the various aspects of robotics and mechanisms, as their links can be modeled easily and compactly as cylinders. This makes tasks such as path planning, determination of the collision-free workspace, etc., computationally easier. © 2016 by ASME.