This paper aims to propose and empirically validate a measure of brand evidence of Online Travel Agencies (OTA), representing all relevant brand associations that customers are doing when evaluating an online brand, and then investigate its effect in building strong consumer-brand relationships and creating favourable consumer behavioural intentions. To check the validity of the proposed model, a survey of 971 users of OTA platforms in Greece was conducted and data was analysed with PLS. Results fully support the validity of the proposed brand evidence index, as several OTA’s brand related associations that a customer develops, before and during service encounters, shape the index expressing brand evidence. Furthermore, the findings confirmed the significant effects of brand evidence on both brand relationships quality and consumer behavioural intentions towards the brand. The current research effort significantly contributes to the field of digital booking services, as it appears to be the first to measure digital brand evidence and investigate their role to strengthen consumer-brand relationships.