When was the first time we knew about Tonks and Lupin's relationship

At the end of Harry Potter and the Half-Blood Prince we get an explicit confirmation

‘But I don’t care either, I don’t care!’ said Tonks, seizing the front of Lupin’s robes and shaking them. ‘I’ve told you a million times …’

And the meaning of Tonks’s Patronus and her mouse-coloured hair, and the reason she had come running to find Dumbledore when she had heard a rumour someone had been attacked by Greyback, all suddenly became clear to Harry; it had not been Sirius that Tonks had fallen in love with after all …

‘And I’ve told you a million times,’ said Lupin, refusing to meet her eyes, staring at the floor, ‘that I am too old for you, too poor … too dangerous …’

‘I’ve said all along you’re taking a ridiculous line on this, Remus,’ said Mrs Weasley over Fleur’s shoulder as she patted her on the back.

‘I am not being ridiculous,’ said Lupin steadily. ‘Tonks deserves somebody young and whole.’

‘But she wants you,’ said Mr Weasley, with a small smile. ‘And after all, Remus, young and whole men do not necessarily remain so.’ He gestured sadly at his son, lying between them.

Eagle-eyed readers will have spotted the clues earlier.

‘Tonks’s Patronus has changed its form,’ he told him. ‘Snape said so, anyway. I didn’t know that could happen. Why would your Patronus change?’