Photo by Andrea Vollmer

Just under two years ago, Berlin's Clara Hill sat with German musician Schneider TM on a makeshift stage overlooking the North Atlantic Ocean, its calm surface lit up by a full moon that trailed light towards the rocks beneath. Between the two musicians and their small audience, a diminutive dancer, Tomoko Nakasato, threw shapes, inspired by the drones of Schneider's electric guitar and the oddly affected vocals which Hill allowed to drift within its textures. It was a hypnotic, impressive performance, and all the more so since their collaboration had apparently only been discussed briefly, during a daytrip round the island upon which the festival at which they were performing, MadeiraDig, was taking place.

What made this impromptu show – which turned out to be one of the highlights of an eye- and ear-opening weekend – even more surprising, and consequently convincing, was the knowledge that, until then, Clara Hill was best known for her work with Sonar Kollektiv, the German label run by DJ and producer collective Jazzanova. She'd released three albums for them: the soulful jazz of 2004's Restless Times, 2006's house-flavoured All I Can Provide, and 2007's more restrained Folkwaves. Her voice was ideal for the polished productions in which the label specialised, its refined, emotive qualities perfect for the soulful grooves that had endeared them to downtempo fans since the late 1990s. Admittedly, any prejudices that might have existed towards its more standard coffee-table context were unlikely to arise: at an event headlined by the likes of Oneohtrix Point Never and Sunn O)))'s Stephen O'Malley, there probably weren't many present who'd heard her records. But anyone aware of them certainly wouldn't have expected her vocals to be manipulated and distorted in such an avant-garde manner. The urbane Sonar Kollektiv vibes and the urban Schneider TM style were at polar ends of the spectrum.

"That night definitively was reassuring," Hill says now of an evening that proved fundamentally important to her. "Everything was possible, and it worked very well. The response of the audience was so positive, it gave me energy to move on. For sure, this night opened the door…"

The door she's referring to is one that led to the significant change of style represented by her fourth album. Walk The Distance is a fascinating and beguiling release, musically located somewhere between the quietest moments of Folkwaves and the sounds she shaped that night on that Portuguese island. Comparing it to her previous work at all seems misleading: you even wonder whether perhaps she might have done better to adopt a new identity to help put her recorded past behind her. That would, however, have been disingenuous. Walk The Distance's tone may repeatedly shift gently yet startlingly – from the likes of 'Dawn Of A New Day' and 'Glacial Moraine', whose rustic airs sometimes sound like those conjured up on Goldfrapp's new release Tales Of Us, to the blurry brushstrokes of the title track and 'Insomnia', whose name perfectly reflects its unsettling narcotic inertia. But it's still clearly the work of the same woman. It's just a huge, brave leap forwards into a musical world that is far truer to her own artistic ambitions than the nu-soul and nu-jazz with which her career started a decade ago.

Clara Hill's first musical experiments began at an early age, growing up in a little village on the edge of East Berlin, where she began playing the Triola, an East German toy harmonica, at the age of two. By the time she was five, she was playing a plastic guitar, graduating to a mini piano a year later. Aged ten, she got her own proper piano, which she proved to have a natural gift for, learning to play Beethoven and Bach by ear during lessons as a teenager. Increasingly fascinated by the rules of harmony, she began writing her own songs, but, despite her formal training, even today she struggles to read music. She ended up in the Sonar Kollektiv world after first combining forces with a friend, Funès, who was playing in a Berlin jazz band. At the age of 17, the two formed acid jazz act Superjuice.

"He was 21 years old," she recalls, "and often took me to his band rehearsals in Kreuzberg [a district in West Berlin]. In the beginning, it was a bit boring for me, because I didn't like the music. It was real jazz. But the more I listened to what the bandleader was trying to play on saxophone, and what he tried to sing, the more I felt I could do it better, and I would sing better than him. So I wrote a melody, and later a text, for a ballad for the band. Funès was so fascinated – and I had so much fun doing this – that we both decided to create our own band with our own music. It was a funny time. We played some small gigs in Berlin, Leipzig and the Eastern part of Germany, as far as I can remember. I was always so nervous, with such heavy stage fright that I never wanted to sing on stage. I'm a shy person, more in the background instead of being a leader. I like to view things from a distance. I often prefer the quiet side of life."

Fortunately, this reticence has subsided over the years. These days, she might even be thought of as less comfortable off the stage than under the spotlight, where she loses herself in her music behind closed eyes. "When I'm on stage," she smiles, "something magical happens. I can break out and get into a special feeling when I'm singing, like I'm in a trance. It's a powerful feeling inside, the same one I get when I'm writing music."

Even back in the days of Superjuice, she can't have been too visibly uncomfortable: after a show in Berlin's venerable Pfefferberg venue, she was approached by Jazzanova's Alex Barck, who expressed his admiration for their work and began to draw her into his universe. So began a partnership that lasted a number of years: she worked with Jazzanova's Stefan Leisering on Restless Times – a "defining" experience, she says now – before its follow up, All I Can Provide, found her joining forces with a host of downtempo luminaries, many of whom were also associated with the Sonar Kollektiv label.

Despite her current musical values, it wasn't an awkward fit. Around the turn of the millennium, Hill had been immersing herself "in 1960s and '70s soul-jazz", and she reels off a list of records that inspired her: Marlena Shaw's 'Look At Me', Antônio Carlos Jobim's Matita Perê, John Lucien's 1991 comeback album Listen Love, and other artists, including Minnie Ripperton, Free Design, Patrice Rushen and James Mason. These passions merged with a growing love for the likes of Matthew Herbert, Roy Ayers and Boards Of Canada, and soon she'd built a solid international fanbase. It was a music that was very much of its time, but though some recordings – like 'Flawless', with its shuffling beats and warped harmonies, or the bare soul of 'Once I Know' – retain a nostalgic appeal, it's clear that even Hill struggles with part of her catalogue these days.

Meeting her in person, it's clear too that the glamorous image she projected back then on her artwork was at odds with her own personality. Just as the musical environment in which she was operating wasn't really where she belonged, so this image was like a mask she had to assume. Additionally, plenty of her musical loves had been sidelined, at least until her third record, for which she was finally able to turn, if only partially, to the likes of Joni Mitchell, Nick Drake and Linda Perhacs. But though Sideways – released under the name Clara Hill's Folkwaves – explored these avenues, and found her reunited with a guitar, it still featured names familiar from her first two releases, and remained stylistically close to them. That Hill seemed to disappear after its release suggested she'd simply given up on finding her voice.

It's now been six years since the release of Sideways. During that time, Hill's been through what she calls "numerous personal changes," as well as returning to her early musical loves. Alongside Perhacs, Drake and Mitchell, these also include, perhaps surprisingly, Tortoise, Helmet and Pavement, plus, she says, rather more psychedelic music from the 1960s. Hill's horizons were also further broadened by her getting involved with the MadeiraDig festival and those behind it. She names artists as diverse as Tim Hecker, Meredith Monk, Cortney Tidwell, John Cage and Ben Frost as having played a role in shaping Walk The Distance.

"I took a long break after the last album," she explains, "which was necessary to reset myself, to balance what is important and what is not. I rediscovered elementary things, working in lo fi-surroundings. It's so good to allow space into the production. I also went back to early sound experiments I did in my childhood. I tried to get back to that feeling of experimenting without any limitations."

Nowadays, Hill refers to her first three albums as "like being in school: you have to learn the basics to have a solid foundation." She displays a confidence that's grown over the past couple of years, in person as well as on record. Indeed, once she gets started, Hill gets almost carried away by the enthusiasm that she has for her newfound creative experiences. Turning her back on Sonar Kollektiv was a risk, but it's obviously been a thrilling one.

"I was tired of polished and flat sounds," she elaborates, "and tired of listening to what others said. I just wanted to release my unborn ideas with my own production. I wanted to break the smooth sound of the past, which sometimes, in retrospect, lacks depth. I wanted get into authenticity and the free development of ideas. Now I can let out ideas which were always inside, but which never found the way out. I think I can express better what I always, over the years, felt."

Since her childhood, music seems always to have been instinctive for Clara Hill, and Walk The Distance represents a fresh opportunity to act independently and listen to those instincts once again. With 'Lost Winter''s rattling drums and smudged vocals sounding like Isn't Anything era My Bloody Valentine, 'Dripstone Cave' echoing the work of (sadly underrated) fellow Berlinerin Barbara Morgenstern – it also features fiercely distorted guitar from Schneider TM – and 'Heading Out' developing slowly into something that sounds like both vintage Stereolab and the toy-pop of Psapp, its roots lie in a past that Hill's neglected far too long. But its pastoral nature, inspired by the likes of Perhacs and Mitchell, serves to emphasise its timeless qualities, especially on the outstanding title track, whose subtle melody remains behind long after it's gone, like a trail frozen into the snow by leaves blown in the wind.

Two years on from that memorable evening in Madeira, Hill's long journey to Walk The Distance seems to have reached its destination. It's a diverse and alluring album that's worthy of close attention: a rugged, fuzzy counterpart to all that it's left behind. "When I was a child I often felt sad and melancholic," Hill concludes. "It was magical and eerie at the same time. I still love dark, sorrowful sounds most. And this is the first time I got the feeling that the work I did was authentic…"

Clara Hill's Walk The Distance is out now via Tapete Records