Sir Keir told the BBC he wanted a “strong showing” in Scotland to be part of a Labour election win.
Labour sources believe the party can win more than 20 seats in Scotland, where the SNP has dominated since 2015.
Two of the target seats high on the Labour list are in West Dunbartonshire, where Martin Docherty-Hughes is currently the MP and Argyll and Bute, which includes Helensburgh and Lomond, and where Brendan O’Hara is the current incumbent.
Dumbarton MSP Jackie Baillie, deputy leader of Labour in Scotland, and Edinburgh’s Ian Murray, currently the only Labour MP left in Scotland, are in charge of electioneering for the party in Scotland.
Senior SNP figures said they were taking Labour’s challenge seriously.
Sir Keir was speaking to Leading Scotland Where?, a BBC Radio 4 programme on the future of Scottish politics following the resignation of First Minister and SNP leader Nicola Sturgeon.
Ms Sturgeon, who was Scotland’s longest-serving first minister, announced in February she was stepping down after more than eight years in the job.
She was succeeded by Humza Yousaf, who narrowly defeated rival Kate Forbes in an SNP leadership contest that exposed deep divisions within the party.
Ms Sturgeon’s husband, Peter Murrell, resigned midway through the leadership campaign after taking responsibility for the party misleading the media about its membership numbers.
The SNP is facing a police investigation into its finances. Mr Murrell was arrested last week as part of the investigation, but was released without charge.
Speaking to the BBC, Sir Keir said Labour had an opportunity to rebuild after the departure of Ms Sturgeon, whom he described as a “formidable” political opponent.
“I want to be not the prime minister of the UK – but the prime minister for the UK,” the Labour leader said.
“That means a strong showing in Scotland, so we have that legitimacy.”
Asked if Labour needed to win a considerable number of seats in Scotland to be seen as prime minister for the whole of the UK, Sir Keir replied: “Yes – it matters to the Labour Party.”
“That’s not translated into a number – but it does mean I need and want to be able to show that we have significant support in Scotland, as we do in Wales and will have across England,” he added.
Within Labour, there’s talk of the party winning 20 or more seats in Scotland at the next general election. But Sir Keir would not commit himself to that number.
The SNP has had the most MPs in Scotland since it won a historic landslide in the 2015 general election victory, taking 56 out of 59 seats.
Its rise came mainly at the expense of Labour, which had held a majority of Scottish seats for decades – but now holds only one, Edinburgh South.
Some SNP politicians have said they are alive to the prospect of a Labour revival in Scotland.
“We have to take it seriously,” the party’s former Westminster leader, Ian Blackford, said.
But he said the SNP – which opposed the UK’s departure from the European Union – had to point out that “Labour are wedded to delivering Brexit”.
He added: “Labour is an alternative to the Tories in the rest of the UK and I get that. I can understand why people would look positively at voting for Labour in such a scenario.
“What we need to do is say there’s a better future for Scotland… by becoming an independent country.”
The party’s deputy leader at Westminster- Mhairi Black – acknowledged “there’s going to be a battle on our hands”.
“I don’t worry about that. If anything, I think the moment you’re not worrying about elections is the moment you become too comfortable.”
She added: “I think there’s a challenge – but bring it on.”
Leading Scotland Where? will be broadcast on BBC Radio 4 at 20:30 on Wednesday 19 April and available on BBC Sounds afterwards
The only way Sir Keir’s Labour Party have a chance of winning in Scotland is if their policies move dramatically to the left.
Sir Keir Starmer is a supporter of NHS Privatisation. He supports the concept of charges for treatment.
Quite how Mr Starmer will attract votes in Scotland for neo Conservative policies like that is very difficult to understand.
Paying for treatment is not popular, and not what the NHS was set up for.
But Starmer is a multi millionaire, like so many of his ilk, and therein lies the gestation as to why private health care is not anathema to him.