Second-half strikes from Coleshill Town's George Washbourne and Jonathan Letford condemned Valley to a disappointing defeat at Butlin Road.
Although the game was fairly evenly contested with few clear cut chances it was Coleshill who secured their first win of 2024 with two well-taken goals.
The hosts made one enforced change from the previous outing at Coventry Sphinx, with Josh Thomas coming into the middle of the Rugby defence in place of the suspended Liam Francis.
The game started with a flurry of chances, with Sam Fitzgerald and Ben O'Hanlon both testing ex-Colemen keeper Paul Hathaway early on, and Chris Cowley also heading one wide within the first six minutes.
For the Valley, Dan Summerfield had also struck one just over the target in the opening exchanges, with Fitzgerald then putting in a long ranger that Hathaway parried and ultimately gathered.
The home side arguably edged the remainder of the half without really threatening to score, although Devonn O'Sullivan did clear the bar with two efforts and also had a well-struck volley blocked by a Coleshill defender.
David Kolodynski was another to fire one way over the frame shortly after Town had seen their shout for a penalty turned away after ex-Valley man Dom Perkins had appeared to handle the ball in the area as MikeyTaylor tried to get a shot off.
Summerfield's strike late in the half was blocked and Chris Clements curled one over, with the final chance of the opening period coming at the other end when O'Hanlon's shot from distance drifted harmlessly wide.
The first proper opportunity after the restart fell to Rugby, when Mike Taylor's rising effort flew agonisingly high of the bar after Silvano Obeng's through ball had released the striker.
The visitors broke the deadlock on 55 minutes though, when Alex Tomlinson's defence-splitting pass enabled Washbourne to apply an impressive finish.
Fitzgerald's low free-kick was then kept out by Hathaway, before a long spell of Valley pressure ensued as they launched their search for an equaliser.
Taylor flicked Jamie Melbourne's free-kick wide, with away keeper Joseph Bevan then intercepting another set-piece into the box to deny the same player.
Harrison Nee's introduction from the bench for his first appearance in a Town shirt saw fresh impetus for the hosts, and he was soon setting up fellow debuting sub Sami Muzaffar for a strike that was blocked, with Summerfield missing out with his speculative volley on the follow-up.
A Nee effort was fumbled by Bevan, with Taylor going down in a challenge for the rebound - but again there was no joy from the match official.
Melbourne's attempt from 25 yards was never troubling Bevan, with Ryan Sahota also firing a shot against the body of a defender as an increasingly-frustrated Rugby began to run out of steam.
Letford had a shot deflected for a corner for the visitors, before Coleshill put the game out of reach when Letford coolly rounded off Cowley's surging run and neat pass with a low finish past Hathaway.
Madundo Semahimbo did have a chance for consolation but his strike was deflected wide after he had shown good pace in a central position, with Taylor also heading one off-target late on.
