The relation between the often reported micellization of petroleum asphaltenes in organic solvents and the content of trace water in the solvent was investigated using calorimetric titration. The content of trace water in toluene (ranging from 0 to 0.047%) was found to be the driving force in establishing a measurable critical micelle concentration in the concentration range between 0.2 and 8 g/L solvent. It was determined that, for the three different asphaltenes analyzed, the calorimetric trace in the presence of 0.018 water more likely indicates a stepwise association rather than a classical micelle formation mechanism. On the basis of this result, the solubilization of water into solutions of asphaltenes in toluene was studied, and a quasi-linear relation between asphaltene concentration and water uptake was observed. From this, the Gibbs free energy of the transference of water into the solution or asphaltene micelle was determined to be around -13.4 kJ/mol at 293 K, which is in the range of hydrogen bonding formation. The solubility of asphaltene in toluene was observed to decrease significantly in water-saturated toluene at room temperature. Finally, the addition of resins (petroleum polar components) to the asphaltene system was found to eliminate the break in the curve previously assigned to CMC. These findings are important for the further understanding of asphaltene self-association, flocculation, and deposition in the oil industry.