<p>This paper introduces a partitioning algorithm for interval data using adaptive distances defined by block variance-covariance matrices. The algorithm has an iterative three-step relocation involving the construction of a partition, identification of a suitable prototype and computation of an adaptive distance by each cluster. In this paper, the distance of each cluster changes at each iteration of the algorithm and it is estimated taking into account joint variance-covariance sub-matrices of the upper and lower boundaries of the interval variables. An experimental evaluation with real and synthetic interval data is performed and the results have confirmed the effectiveness of the proposed algorithm. Moreover, insights about Brazilian interval temperature data clustering are extracted from an application of the algorithm regarding interpretation indices of the cluster analysis for interval data.</p>